// @题目描述
// 给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:
// 创建一个根节点，其值为 nums 中的最大值。
// 递归地在最大值 左边 的 子数组前缀上 构建左子树。
// 递归地在最大值 右边 的 子数组后缀上 构建右子树。
// 返回 nums 构建的 最大二叉树 
// @题目链接：https://leetcode.cn/problems/maximum-binary-tree

// 递归解决（O(N^2),O(N)）
class Solution {
public:
    TreeNode* constructHelper(vector<int>::iterator beg,vector<int>::iterator end,vector<int>& nums){
        // 如果数组为空，返回空指针
        if(beg == end)  return nullptr;
        // 当前部分只有一个节点则直接构造，不再求最大值
        if(end-beg == 1)    return new TreeNode(*beg);
        // 求最大值的迭代器
        auto maxIndex = max_element(beg,end);
        int maxVal = *maxIndex;
        TreeNode* root = new TreeNode(maxVal);
        // 分别构造左右子树
        root->left = constructHelper(beg,maxIndex,nums);
        root->right = constructHelper(maxIndex+1,end,nums);
        return root;
    }
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        return constructHelper(nums.begin(),nums.end(),nums);
    }
};